The present invention relates to techniques for performing timing analysis of a user design for a programmable integrated circuit, and more particularly, to techniques for determining whether a placement for a user design satisfies timing constraints without analyzing unnecessary timing paths by using edge masks.
A programmable integrated circuit (IC) is a circuit that contains numerous programmable circuit elements called logic blocks or logic elements. The logic blocks can be programmed to implement a variety of logic functions. Programmable ICs also include memory blocks and programmable routing resources that can be programmed to connect the memory blocks and logic elements.
Programmable ICs include field programmable gate arrays (FPGAs), programmable logic devices (PLDs), programmable logic arrays (PLAs), configurable logic arrays, mask programmable logic devices, etc. Programmable integrated circuits can also contain hardwired circuit blocks that are not programmable.
A programmable IC as a whole can be programmed according to a circuit schematic designed by a user (i.e., a user design). The user design is initially converted into a network of abstract logic elements that can be mapped directly onto the programmable IC. The conversion process is referred to as synthesis.
Actual logic elements on the programmable IC are then identified to implement the abstract logic elements generated during synthesis. This identification process is referred to as placement. Subsequently, the programmable routing resources are programmed to connect together the logic elements during a routing process.
Typically a user specifies timing constraints that are intended to regulate the operation of a programmable IC user design. The timing constraints are time limits that indicate the minimum allowable clock speeds or maximum allowable point-to-point delays for various portions of the user design.
The placement process greatly affects timing delays in the user design. If two logic elements that are connected together in the user design along a time critical path are placed far apart from each other on the programmable IC, the delay for a signal to pass between these two logic elements may exceed one of the user's timing constraints.
Once a user design has been placed onto the logic elements during the placement process timing analysis is performed on the user design. Timing analysis uses either breadth-first search (BFS) or depth-first search (DFS) techniques. The goal of the analysis is to identify maximum delay paths between selected source points and destination points in a user circuit design relative to each constraint or constraint type. A critical path is a directed path in the placed design that has the longest signal delay time from a source point to a destination point either in absolute terms or relative to its constraint.
Breadth-first search is more advantageous for minimizing the additional work required to visit nodes which are not relevant to a computation. However, BFS must propagate multiple delay values per node, and this can significantly increase computer memory use. Recursive DFS can mitigate memory use, but can require searching more of the netlist than BFS, and is thus computationally more expensive.
Timing analysis also involves calculating slack and relative slack or slack ratio for certain timing critical circuit paths in the user design. These values are used to aid the placement tool. If the timing delay along one or more of the time critical paths exceeds the user's timing constraints, some or all of the user design is placed into different logic elements on the programmable IC to improve the timing delay of the user design.
Performing depth first searches through a very large number of circuit paths and interconnections in a user design for a programmable IC can be time consuming. When a depth first search is performed on a user design, the timing analysis tool does not know which circuit paths will lead to the source point or the destination point. Therefore, timing analysis tools analyzes all circuit paths that lead in a particular direction during a depth first search.
Therefore, it would be desirable to provide faster and more efficient techniques for performing timing analysis of placed user designs for programmable ICs. The present invention provides a technique to improve the time taken by DFS to allow comparable time-complexity to BFS without the additional memory overhead, and further provides other beneficial properties.